/*
145. 二叉树后序遍历
左右中的顺序，要直接通过一个辅助栈很难实现，因为一个辅助栈只能到达一个节点2次(入栈出栈)
可以改变前序遍历的逻辑，达到中右左的顺序，再通过一个栈来实现倒序为左右中
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
  const result = []
  const stack = []
  const reverseStack = []
  if (root) {
    stack.push(root)
    while (stack.length) {
      const node = stack.pop()
      if (node) {
        reverseStack.push(node.val)
        stack.push(node.left)
        stack.push(node.right)
      }
    }
    while (reverseStack.length) {
      result.push(reverseStack.pop())
    }
  }
  return result
}

var postorderTraversal2 = function (root) {
  const result = []
  if (root) {
    const stack = []
    stack.push(root)
    let cur = null // 用于表示当前要弹出的节点
    while (stack.length) {
      cur = stack[stack.length - 1]
      if (cur.left && root !== cur.left && root !== cur.right) {
        // 这里是判断第一次访问这个节点，因为上一次弹出(打印)的节点既不是当前节点左子树也不是右子树,应该先压入左
        stack.push(cur.left)
      } else if (cur.right && root !== cur.right) {
        // 这里是第二次到达当前节点，之前弹出的是当前节点的左子树
        stack.push(cur.right)
      } else {
        // 第三次到达该节点，弹出该节点打印
        result.push(cur.val)
        stack.pop()
        root = cur // root是用来记录从哪个节点返回的
      }
    }
  }
  return result
}
